package com.feng.study.demo.sort;


import java.util.Arrays;

/**
 * @Author: Zeng ShaoYong
 * @Date: 2022-01-04
 * @Description:
 */
public class SortDemo01 {
    public static void main(String[] args) {
        demo01();
    }

    private static void demo01() {
        int[] nums = {3, 4, 1, 6, 5, 2, 8, 9, 7};
//        sort01(nums);
//        sort02(nums);
//        sort03(nums);

//        selected(nums);

//        insert(nums);
        insert02(nums);
    }

    /**
     * 冒泡
     */
    private static void sort01(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                }
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 冒泡优化一
     */
    private static void sort02(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            boolean b = true;
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    b = false;
                }
            }
            if (b) {
                break;
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 冒泡优化二
     */
    private static void sort03(int[] nums) {
        int n = nums.length - 1;
        while (true) {
            int temp = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    temp = j;
                }
            }
            n = temp;
            if (n == 0) {
                break;
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 选择排序
     */
    private static void selected(int[] nums){
        for (int i = 0; i <nums.length-1; i++) {
            int temp=i;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[temp]>nums[j]){
                    temp=j;
                }
            }
            if (temp!=i){
                swap(nums,i,temp);
            }
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 插入排序
     */
    private static void insert(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            //已排序的数组
            int j=i-1;
            //待插入的元素
            int a=nums[i];
            //找到插入的位置j
            while (j>=0){
                if (a<nums[j]){
                    nums[j+1]=nums[j];
                }else {
                    //优化，提前结束循环
                    break;
                }
                j--;
            }
            nums[j+1] = a;
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 插入优化二，二分查找
     */
    private static void insert02(int[] nums){
        for (int i = 1; i <nums.length ; i++) {
            //待插入的元素
            int a=nums[i];
            //已经有序left--right
            int left=0;
            int right=i-1;
            //找到插入的位置j
            while (left<=right){
                int mid=left+(right-left)/2;
                if (nums[mid]>a){
                    right=mid-1;
                }else {
                    left=mid+1;
                }
            }
            for (int j = i-1; j >=left ; j--) {
                nums[j+1]=nums[j];
            }
            nums[left]=a;
        }
        System.out.println(Arrays.toString(nums));
    }

    /**
     * 交换
     */
    private static void swap(int[] nums, int i, int j) {
        int a = nums[i];
        nums[i] = nums[j];
        nums[j] = a;
    }
}
